package com.wwz.leetcode;

import java.util.Arrays;


//老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
//
//你需要按照以下要求，帮助老师给这些孩子分发糖果：
//
//每个孩子至少分配到 1 个糖果。
//评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。
//那么这样下来，老师至少需要准备多少颗糖果呢？
//输入: [1,2,2]
//        输出: 4
//        解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
//        第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

public class LeetCode135 {

    //int[] ratings = {1, 2, 87, 87, 87, 2, 1};   sout  13
    //int[] ratings = {1,3,4,5,2};   sout  11
    //int[] ratings = {1, 3, 2, 2, 1}; sout 7
    //int[] ratings = {1,6,10,8,7,3,2}; sout 18

    public static void main(String[] args) {
        int[] ratings = {1, 6, 10, 8, 7, 3, 2};
        //int[] ratings = {1,3,4,5,2};
        //int[] ratings = {3, 2, 1, 1, 4, 3, 3};
        //int[] ratings = {1, 0, 2};
        //int[] ratings = {1, 2, 2};
        //int[] ratings = {1, 2, 87, 87, 87, 2, 1};
        //int[] ratings = {1, 3, 4, 5, 2};
        System.out.println(candy(ratings));
    }

    //    public static int candy(int[] ratings) {
//        int[] left = new int[ratings.length];
//        int[] right = new int[ratings.length];
//        Arrays.fill(left, 1);
//        Arrays.fill(right, 1);
//        for(int i = 1; i < ratings.length; i++)
                //先满足左规则
//            if(ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
//        int count = left[ratings.length - 1];
//        for(int i = ratings.length - 2; i >= 0; i--) {
               //先满足右规则
//            if(ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
                //贪心 取都满足的部分
//            count += Math.max(left[i], right[i]);
//        }
//        return count;
//    }
    public static int candy(int[] ratings) {
        //每人先发一颗
        int[] array = new int[ratings.length];
        Arrays.fill(array, 1);
        for (int i = 0; i < ratings.length; i++) {
            //右面有数字
            if (i + 1 < ratings.length) {
                //自身比右大 就加一个
                if (ratings[i] > ratings[i + 1]) {
                    array[i] = array[i + 1] + 1;
                    recursionCheck(i,array,ratings);
                    continue;
                }
            }
            //左边有数字
            if (i - 1 >= 0 && i <= ratings.length - 1) {
                //自身比左大 就加一个
                if (ratings[i - 1] < ratings[i]) {
                    array[i] = array[i - 1] + 1;
                }
            }

        }
        int sum = 0;
        for (int i : array) {
            sum += i;
        }
        return sum;
    }

    /**
     * @Description: 递归校验
     * @create: 2021-07-13 22:08:09
     * @author:wwz
     */
    public static void recursionCheck(int i, int[] array, int[] ratings){
        int j = i;
        while (j - 1 >= 0) {
            while (array[j] >= array[j - 1] && ratings[j] < ratings[j - 1]) {
                array[j - 1] = array[j] + 1;
                j--;
                //防止越界
                if (j - 1 < 0) {
                    break;
                }
            }
            if (j - 1 >= 0) {
                while (array[j] <= array[j - 1] && ratings[j] > ratings[j - 1]) {
                    array[j] = array[j - 1] + 1;
                    j--;
                    if (j - 1 < 0) {
                        break;
                    }
                }
            }
            j--;
        }
    }

}
